#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int N = 1e6 + 10;

int a, n;
int vis[N];

void dfs(int x, int d) {
    // cout << x << ',' << d << endl;
    vis[x] = d;
    if (x == 1) {
        return;
    }
    if (x % a == 0) {
        int nxt = x / a;
        if (nxt > 0 && vis[nxt] > d + 1) dfs(nxt, d + 1);
    }

    if (x >= 10) {
        int b = 1;
        while (b < x) {
            b *= 10;
        }
        b /= 10;
        int u = x / b, v = x % b;
        int nxt = v * 10 + u;
        if (nxt > 0 && v >= b / 10&& vis[nxt] > d + 1) dfs(nxt, d + 1);
    }
}
int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    memset(vis, 0x3f, sizeof(vis));
    cin >> a >> n;

    dfs(n, 0);

    if (vis[1] == 0x3f3f3f3f) vis[1] = -1;
    cout << vis[1] << endl;

    return 0;
}